/*
MIT License

Copyright (c) 2021 МГТУ им. Н.Э. Баумана, кафедра ИУ-6, Михаил Фетисов,

https://bmstu.codes/lsx/simodo/loom
*/

#include "simodo/interpret/builtins/hosts/fuze/ParsingTableBuilder_abstract.h"

#include "simodo/inout/convert/functions.h"
#include "simodo/inout/format/fmt.h"

#include <algorithm>
#include <cassert>

namespace simodo::interpret::builtins
{
    bool ParsingTableBuilder_abstract::build(const std::vector<parser::GrammarRuleTokens> &rules, const inout::Token &main_rule)
    {
        if (rules.empty())
        {
            _m.reportError( inout::null_location, 
                            inout::fmt("Не заданы правила грамматики '%1'")
                            .arg(_grammar_name));
            return false;
        }

        inout::Token main_production = (main_rule.token().empty() ? rules[0].production : main_rule);

        // Добавляем обобщённое правило
        std::vector<inout::Token> pattern {
            { inout::LexemeType::Compound, main_production.token(), main_production.location() },
            { inout::LexemeType::Empty, u"", main_production.location() },
        };
        _rules.push_back({ inout::Token { inout::LexemeType::Compound, main_production.token()+u"'", main_production.location() },
                        pattern,
                        ast::Node(),
                        parser::RuleReduceDirection::Undefined });

        // Вытягиваем из заданных правил грамматики только те, что относятся к основному правилу
        if(!extractRules(rules, main_production.token()))
            return false;

        if (_rules.size() <= 1)
        {
            _m.reportError( main_production.makeLocation(_files),
                            inout::fmt("Не удалось извлечь правила грамматики '%1'")
                            .arg(_grammar_name));
            return false;
        }

        // Заполняем индекс продукций для правил грамматики
        for(size_t i=0; i < _rules.size(); ++i)
            _production_index.emplace(_rules[i].production.token(),i);

        // Заполняем индекс символов из образца для правил грамматики
        for(size_t i=0; i < _rules.size(); ++i)
            for(const inout::Lexeme & s : _rules[i].pattern)
                if (s.type() == inout::LexemeType::Compound)
                {
                    // Повторы пар (s, индекс на правило) нам не нужны - проверяем на наличие
                    auto   range = _pattern_index.equal_range(s.lexeme());
                    auto & it    = range.first;
                    for(; it != range.second; ++it)
                        if (it->second == i)
                            break;

                    if (it == range.second)
                        _pattern_index.emplace(s.lexeme(),i);
                }

        // Проверяем какие правила не были собраны (не используются)
        if (_rules.size() <= rules.size())
            for(const parser::GrammarRuleTokens & r : rules)
                if (_production_index.end() == _production_index.find(r.production.token()))
                    _m.reportWarning(r.production.makeLocation(_files),
                                inout::fmt("Нетерминал '%1' не используется в грамматике '%2'")
                                .arg(r.production.token())
                                .arg(_grammar_name));

        // Проверяем, что все нетерминалы имеют продукции
        bool ok = true;
        for(const auto & [p,i] : _pattern_index)
        {
            std::u16string last;
            if (last != p)
            {
                if (_production_index.find(p) == _production_index.end())
                {
                    assert(i < _rules.size());
                    size_t j = 0;
                    for(; j < _rules[i].pattern.size(); ++j)
                        if (p == _rules[i].pattern[j].token())
                            break;

                    inout::Token t = (j < _rules[i].pattern.size()) ? _rules[i].pattern[j] : _rules[i].production;

                    _m.reportError(t.makeLocation(_files),
                                inout::fmt("Нетерминал '%1' не имеет продукции для грамматики '%2'")
                                .arg(p)
                                .arg(_grammar_name));
                    ok = false;
                }
                last = p;
            }
        }
        if (!ok)
            return false;

        // Копируем _rules в _g.rules для работы наследуемого кода (всё равно нужно копировать)
        for(const parser::GrammarRuleTokens & r : _rules)
        {
            std::vector<inout::Lexeme> p;

            for(const inout::Token & t : r.pattern)
                p.push_back(t);

            _g.rules.emplace_back(r.production.token(), p, r.reduce_action, r.reduce_direction);
        }

        // Заполняем перечень состояний автомата разбора
        fillStateTable();

        // Вычисляем границу для значений таблицы разбора
        assert(std::max(_g.rules.size(),_g.states.size()) < UINT32_MAX/5);
        _g.value_bound = static_cast<parser::Fsm_value_t>(std::max(_g.rules.size(),_g.states.size())) + 1;

        // Заполняем значения колонок
        fillColumns();

        // Определяем "вычисляемые" параметры лексики
        fillLexemeParameters(_g);

        // Вычисляем границу для ключа таблицы разбора
        assert(_g.columns.size()*_g.states.size() < UINT32_MAX/2);
        _g.key_bound = static_cast<parser::Fsm_key_t>(_g.columns.size()) + 1;

        // Формируем таблицу разбора
        if (!fillParseTable())
            return false;

        // Проверяем полноту наполнения
        return checkCompleteness();
    }

    bool ParsingTableBuilder_abstract::extractRules(const std::vector<parser::GrammarRuleTokens> &rules, std::u16string production)
    {
        size_t rule_no = 0;
        size_t patt_no = 0;

        _rules.reserve(rules.size());

        while(!production.empty())
        {
            // Вытягиваем все связанные с заданной продукцией правила
            for(const parser::GrammarRuleTokens & r : rules)
                if (r.production.token() == production)
                {
                    // Убеждаемся, что это правило не дубль
                    size_t i = 0;
                    for(; i < _rules.size(); ++i)
                    {
                        if (_rules[i].production.token() != production)
                            continue;

                        if (_rules[i].pattern.size() != r.pattern.size())
                            continue;

                        size_t j = 0;
                        for(; j < _rules[i].pattern.size(); ++j)
                            if (_rules[i].pattern[j] != r.pattern[j])
                                break;

                        if (j == _rules[i].pattern.size())
                            break;
                    }
                    if (i != _rules.size())
                        continue;

                    // Добавляем правило в грамматику
                    _rules.push_back(r);
                }

            production = u"";

            // Специально избавляемся от рекурсии, чтобы упорядочить перечень правил по продукциям
            do
            {
                patt_no ++;

                if (patt_no == _rules[rule_no].pattern.size())
                {
                    rule_no ++;

                    if (rule_no == _rules.size())
                        break;

                    patt_no = 0;
                }

                assert(!_rules[rule_no].pattern.empty());

                if (_rules[rule_no].pattern[patt_no].type() == inout::LexemeType::Compound)
                {
                    // Сначала убеждаемся, что этого нетерминала нет в нашем списке (оптимизируем)
                    const std::u16string & att_prod = _rules[rule_no].pattern[patt_no].lexeme();

                    size_t i=1;
                    for(; i < _rules.size(); ++i)
                        if (_rules[i].production.token() == att_prod)
                            break;

                    // Не нашли, значит обрабатываем
                    if (i == _rules.size())
                        production = att_prod;
                }
            }
            while(production.empty());
        }

        return true;
    }

    void ParsingTableBuilder_abstract::fillColumns() const
    {
        // Сначала заполняются терминальные символы грамматики
        for(const parser::GrammarRule & r : _g.rules)
            for(const inout::Lexeme & s : r.pattern)
                if (s.type() != inout::LexemeType::Compound)
                    if (find(_g.columns.begin(),_g.columns.end(),s) == _g.columns.end())
                        _g.columns.push_back(s);

        // Затем идут нетерминалы
        _g.first_compound_index = _g.columns.size();

        for(const parser::GrammarRule &r : _g.rules)
            for(const inout::Lexeme & s : r.pattern)
                if (s.type() == inout::LexemeType::Compound)
                    if (find(_g.columns.begin(),_g.columns.end(),s) == _g.columns.end())
                        _g.columns.push_back(s);
    }

    bool ParsingTableBuilder_abstract::checkCompleteness()
    {
        bool ok = true;

        // Проверяем, что все приведения попали в таблицу
        // (правило 0 не должно участвовать)
        for(size_t i=1; i < _g.rules.size(); ++i)
        {
            bool found = false;
            for(const auto & [key,value] : _g.parse_table)
            {
                parser::FsmActionType action   = _g.unpackFsmAction(value);
                size_t                location = _g.unpackFsmLocation(value);

                if (action == parser::FsmActionType::Reduce)
                    if (location == i)
                    {
                        found = true;
                        break;
                    }
            }
            if (!found)
            {
                assert(i < _rules.size());
                _m.reportFatal( _rules[i].production.makeLocation(_files),
                                inout::fmt("Правило %1 грамматики '%2' не участвует в разборе.")
                                .arg(i)
                                .arg(_grammar_name));
                ok = false;
            }
        }

        return ok || !_strict_rule_consistency;
    }

}